#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from pptree import print_tree


class TreeNode:
    __slots__ = ['value', 'left', 'right', 'children']

    def __init__(self, value):
        self.value = value
        self.children = []
        self.left, self.right = None, None

    @property
    def lr(self):
        l = []
        if self.left:
            l.append(self.left)

        if self.right:
            l.append(self.right)
        return l

    def __str__(self):
        return str(self.value)


class Tree():
    __slots__ = ['root']

    def __init__(self, root):
        self.root = root

    def binarize(self):
        self._binarize_node(self.root)

    def _binarize_node(self, node):
        if not node.children:
            return

        # set node's left + children's right
        node.left = left = node.children[0]

        for sibling in node.children[1:]:
            left.right = sibling
            left = sibling

        # process node's children: recursive
        for c in node.children:
            self._binarize_node(c)

        node.children.clear()

    def childrenize(self):
        if self.root.children:
            return

        self._childrenize_node(self.root)

    def _childrenize_node(self, node):
        ''' 二叉树转为孩子节点 '''
        left = node.left
        if left:
            node.children.append(left)

            while left.right:
                right = left.right
                node.children.append(right)
                left = right

        if node.left:
            self._childrenize_node(node.left)
        if node.right:
            self._childrenize_node(node.right)

        node.left, node.right = None, None

    def show(self):
        node = self.root
        if node.children:
            print('show children')
            return self._show_children(node)
        else:
            print('show left right')
            return self._show_left_right(node)

    def _show_children(self, node):
        ''' children的先序遍历 == 转为二叉树后的二叉树的中序遍历 '''
        print(node)
        for c in node.children:
            self._show_children(c)

    def _show_left_right(self, node):
        ''' 中序遍历 '''
        print(node)
        if node.left:
            self._show_left_right(node.left)

        if node.right:
            self._show_left_right(node.right)

def build_tree():
    root = TreeNode(0)
    for i in range(1, 10):
        # root.children = [TreeNode(1), TreeNode(2), TreeNode(3), TreeNode(4), TreeNode(5), TreeNode(5)]
        root.children.append(TreeNode(i))

    v = 3
    for c in root.children:
        c.children = [TreeNode(v+1), TreeNode(v+2), TreeNode(v+3)]
        v += 3

    return Tree(root)

def test_binarize():
    # origin
    tree = build_tree()
    # tree.show()
    print_tree(tree.root, 'children')

    # binarize
    tree.binarize()
    # tree.show()
    print_tree(tree.root, 'lr')

    # childrenize
    tree.childrenize()
    tree.show()

    # binarize
    tree.binarize()
    tree.show()

def main():
    print("start main")

    root = test_binarize()


if __name__ == "__main__":
    main()
